package exam.xiaozuduikang.exam2019;

import exam.xiaozuduikang._0419mergeList;

import java.util.ArrayList;
import java.util.List;

public class MergeList {

    public static void main(String[] args) {
ListNode a1=new ListNode(1);
      ListNode a2=new ListNode(4);
      ListNode a3=new ListNode(5);
        a1.next=a2;
        a2.next=a3;
        a3.next=null;

        ListNode aa1=new ListNode(1);
       ListNode aa2=new ListNode(3);
        aa1.next=aa2;
        aa2.next=null;


        ListNode listRes=mergeTwoLists(a1,aa1);
    }

    public List<Node> mergeListMethod(ArrayList<Node> a1, ArrayList<Node> a2) {
        if (a1 == null && a2 == null) {
            return null;
        } else if (a1 == null && a2 != null) {
            return a2;
        } else if (a1 != null && a2 == null) {
            return a1;
        }
        int lenA1 = a1.size();
        int lenA2 = a2.size();
        int sumLen = 0;
        int curA1 = 0;
        int curA2 = 0;
        List<Node> mergeRes = new ArrayList<Node>();
        while (curA1 < lenA1 && curA2 < lenA2) {
            if (a1.get(curA1).value <= a2.get(curA2).value) {
                mergeRes.add(a1.get(curA1));
                curA1++;
            } else {
                mergeRes.add(a2.get(curA2));
                curA2++;
            }
        }
        if (curA1 < lenA1) {
            for (int i = curA1; i < lenA1; i++) {
                mergeRes.add(a1.get(curA1));
                curA1++;
            }
        }
        if (curA2 < lenA2) {
            for (int i = curA2; i < lenA2; i++) {
                mergeRes.add(a2.get(curA2));
                curA2++;
            }
        }
        return mergeRes;
    }

    /**
     * Definition for singly-linked list.
     * public class ListNode {
     * int val;
     * ListNode next;
     * ListNode(int x) { val = x; }
     * }
     */
    static class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
        }
    }

    public static ListNode mergeTwoLists(ListNode a1, ListNode a2) {
        if (a1 == null && a2 == null) {
            return null;
        } else if (a1 == null && a2 != null) {
            return a2;
        } else if (a1 != null && a2 == null) {
            return a1;
        }
        ListNode mergeResCur=new ListNode(0);
        ListNode mergeResHead=mergeResCur;
        while (a1!=null&& a2!=null ) {
            if (a1.val<= a2.val) {
                mergeResCur.next=a1;
                mergeResCur=mergeResCur.next;
                a1=a1.next;
            } else {
                mergeResCur.next=a2;
                mergeResCur=mergeResCur.next;
                a2=a2.next;
            }
        }
        if (a1!=null) {
            mergeResCur.next=a1;
        }
        if (a2!=null) {
            mergeResCur.next=a2;
        }
        return mergeResHead.next;
    }
}
